package basicSort.mergeSort;

/**
 * 基本归并排序  分治思想   空间复杂度O(n) 时间复杂度 O(nlogn)  是个稳定排序
 * 由于归并排序的算法复杂度的常数项比较大 因此 在小数据中不推荐用,小数据应用插入排序
 * 归并排序和快速排序 : 归并排序适用于部分有序的结构,而快速排序适用乱序的结构
 * 归并排序 稳定性 非原址排序
 * 快速排序 非稳定性 原址排序
 */

public class MergeSort {

    public static int[] merge(int[] arr){

        deliver(arr,0,arr.length-1);

        return arr;
    }

    //分治
    public static void deliver(int[] arr , int l,int r){
        if(l<r){
            int mid = l + (r-l)/2;
            deliver(arr,l,mid);
            deliver(arr,mid+1,r);
            merge(arr , l , mid , r);
        }
    }

    //归并
    public static void merge(int[] arr , int l , int mid , int r){
        int[] arrTemp = new int[r-l+1];
        int left = l;
        int right = mid + 1;
        int i = 0;
        while( left<=mid && right<=r ){
            arrTemp[i++] = arr[left]<=arr[right]?arr[left++]:arr[right++];
        }
        while(left<=mid){
            arrTemp[i++]=arr[left++];
        }
        while(right<=r){
            arrTemp[i++]=arr[right++];
        }
        for(int in = 0 ;in < i;in++){
            arr[l+in] = arrTemp[in];
        }
    }

}
